package newcoder_exp.justPractise;
import java.util.*;

import org.junit.Test;
public class NC97 {
    public class Solution {
        /**
         * return topK string
         * @param strings string字符串一维数组 strings
         * @param k int整型 the k
         * @return string字符串二维数组
         */
        public String[][] topKstrings (String[] strings, int k) {
            int len = strings.length;
            if (k == 0) return new String[len][2];
            Queue<Node> queue = new PriorityQueue<>((n1, n2) -> {
                int res1 = n1.times - n2.times;
                if (res1 != 0) return res1;
                else return n1.s.compareTo(n2.s);
            });
            Map<String, Node> map = new HashMap<>();
            for (int i = 0; i < len; i++) {
                if (map.containsKey(strings[i])) {
                    map.get(strings[i]).times++;
                } else {
                    map.put(strings[i], new Node(strings[i]));
                }
            }
            // if (map.size() <= k) {
            //     return change(map);
            // }
            // Map<String, Node> newMap = new HashMap<>();
            // newMap.putAll(map);
            for (String s: map.keySet()) {
                if (queue.size() == k && queue.peek().times < map.get(s).times) {
                    Node node = queue.poll();
                    // newMap.remove(node.s);
                }
                if (queue.size() < k)
                    queue.offer(map.get(s));
            }
            String[][] res = new String[queue.size()][2];
            int idx = queue.size() - 1;
            while (!queue.isEmpty()) {
                Node n = queue.poll();
                res[idx][0] = n.s;
                res[idx][1] = n.times + "";
                idx--;
            }
            return res;
        }
        
        public String[][] change(Map<String, Node> map) {
            String[][] res = new String[map.size()][2];
            int idx = 0;
            for (String s: map.keySet()) {
                res[idx][0] = s;
                res[idx][1] = map.get(s).times + "";
                idx++;
            }
            return res;
        }
        
        class Node {
            String s;
            int times;
            public Node(String s) {
                this.s = s;
                this.times = 1;
            }
        }
    }


    @Test
    public void test() {
        Solution s = new Solution();
        String[] strs = {"abcd","abcd","abcd","pwb2","abcd","pwb2","p12"};
        String[][] res = s.topKstrings(strs, 3);
        System.out.println(Arrays.deepToString(res));
    }
}
